class Solution {
    // 使用动态规划的思想来解决
    public String longestPalindrome(String s) {
        // 创建dp表、初始化、填表、返回值
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        char[] ss = s.toCharArray();

        // 初始化的工作通过 for循环 完成
        int[] ret = new int[2]; // 记录最长回文子串的起始位置和结束位置
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j >= i; j--) {
                if (ss[i] == ss[j]) {
                    if (i == j || i+1 == j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                // 更新最长回文子串的信息
                if (dp[i][j] && j - i > ret[1] - ret[0]) {
                    ret[0] = i;
                    ret[1] = j;
                }
            }
        }

        return s.substring(ret[0], ret[1]+1);
    }
}